package com.origin.niuke.array;

import java.util.Arrays;

/**
 * NC77 调整数组顺序使奇数位于偶数前面(一)
 * 算法：插入排序
 *
 * @author yezh
 * @version 1.0
 * @date 2022/11/1 21:50
 */
public class NC77 {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new NC77().reOrderArray(new int[]{1, 2, 3, 4})));
    }

    public int[] reOrderArray (int[] array) {
        // write code here
        int n = array.length;
        for (int i = 1; i < n; i++) {
            if (array[i] % 2 != 0) {
                int insertValue = array[i];
                int idx = i - 1;
                while (idx >= 0 && array[idx] % 2 == 0) {
                    array[idx + 1] = array[idx];
                    idx--;
                }
                array[idx + 1] = insertValue;
            }
        }
        return array;
    }

}
